package hl.leco;

import java.util.*;

/*
这道题主要用到思路是：滑动窗口     什么是滑动窗口？

其实就是一个队列,比如例题中的 abcabcbb，进入这个队列（窗口）为 abc 满足题目要求，
当再进入 a，队列变成了 abca，这时候不满足要求。所以，我们要移动这个队列！

如何移动？
我们只要把队列的左边的相同元素之前的值删除，然后继续移动，直到满足题目要求！

一直维持这样的队列，找出队列出现最长的长度时候，求出解！

时间复杂度：O(n)
*/

public class WuChongFuZiChuan {

    public static void lengthOfLongestSubstring(String s) {
        // 遍历打印字符串
        for (int i=0; i<s.length(); i++)    // 遍历字符串
            System.out.print(s.charAt(i));  // 打印字符
        System.out.println();

        // 创建一个 HashMap 实例 map，用来存储 键值对   字符->数值
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        int max = 0;
        int left = 0;
        for(int i = 0; i < s.length(); i ++){   // 遍历字符串
            if(map.containsKey(s.charAt(i))){   // 如果 这个 map 中有这个字符
                //left = Math.max(left,map.get(s.charAt(i)) + 1);
                left = map.get(s.charAt(i)) + 1;
                System.out.println("left = " + left);
            }
            map.put(s.charAt(i),i);         // 构建 键值对，存入 map
            System.out.println(map);
            max = Math.max(max,i-left+1);   //
            System.out.println("max = " + max);
        }
        System.out.println("max = " + max);
    }

    public static void main (String args[]){

        String ss = "abba";
        lengthOfLongestSubstring(ss);
    }

}
